package com.hecun.algorithm.tree;

import java.util.LinkedList;
import java.util.Queue;

public class Demo2 {
	/**
	 * 打印二叉树每个节点所在的层数
	 */
	public static void printLevel(TreeNode root){
		preOrder(root, 1);
	}
	
	public static void preOrder(TreeNode p, int level) {
		if (p != null) {
			System.out.println(p.val + " " + level);
			preOrder(p.left, level + 1);
			preOrder(p.right, level + 1);
		}
	}
	
	/**
	 * 最大深度
	 */
	public int maxDepth(TreeNode root) {
		return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
	}
	
	/**
	 * 最小深度
	 */
	public int min = Integer.MIN_VALUE / 2;
	public int minDepth(TreeNode root) {
		if (root == null) {
			return 0;
		}
		preOrder(root, 1);
		return min;
	}
	public void preOrder2(TreeNode p, int level) {
		if (p != null) {
			if (p.left == null && p.right == null) {
				if (level < min) {
					min = level;
				}
			}
		}
		preOrder(p.left, level + 1);
		preOrder(p.right, level + 1);
	}
	
	/**
	 * 反转二叉树
	 */
	public TreeNode invertTree(TreeNode root) {
		postOrder(root);
		return root;
	}
	public void postOrder(TreeNode p) {
		if (p != null) {
			postOrder(p.left);
			postOrder(p.right);
			TreeNode temp = p.left;
			p.left = p.right;
			p.right = temp;
		}
	}
	
	/**
	 * 统计结点个数，后序遍历法
	 */
	public int postOrder2(TreeNode node){
		if(node==null){
			return 0;
		}else{
			int leftCnt=postOrder2(node.left);
			int rightCnt=postOrder2(node.right);
			return leftCnt+rightCnt+1;
		}
	}
	
	/**
	 * 统计叶子节点个数，中序遍历法
	 */
	int count = 0;
	public void inOrder(TreeNode node){
		if(node!=null){
			inOrder(node.left);
			if(node.left==null&&node.right==null){
				count++;
			}
			inOrder(node.right);
		}
	}
	
	/**
	 * 统计值为x的节点个数，层序遍历法
	 */
	public void levelOrder(TreeNode root,Integer x){
		Queue<TreeNode> queue=new LinkedList<TreeNode>();
		queue.offer(root);
		int cnt=0;
		
		while(!queue.isEmpty()){
			TreeNode node=queue.poll();
			
			if(node.val == x){
				cnt++;
			}

			if(node.left!=null){
				queue.offer(node.left);
			}
			if(node.right!=null){
				queue.offer(node.right);
			}
		}
		System.out.println(cnt);
	}
}
